1 /* 2 * Copyright (c) 2012-2013 Nonki Takahashi. All rights reserved. 3 * 4 * History: 5 * 0.5 2013-06-15 Supported JsDoc Toolkit. 6 * 0.4 2013-03-16 Supported row vector. Treated row vector as matrix. 7 * 0.3 2012-05-17 Tuned mothod mul. 8 * 0.2 2012-05-16 Corrected the other way around row and column in method toString 9 * 0.1 2012-05-14 Created. Ported from Java version. 10 */ 11 12 /** 13 * @fileOverview BMatrix - Binary Matrix Object 14 * @name bmatrix05.js 15 * @version 0.5 16 * @author Nonki Takahashi 17 * 18 */ 19 20 /** 21 * Binary Matrix Object 22 * @example 23 * bm = new BMatrix(2, 2); // 2-row 2-column binary matrix (0 0 ↓ 0 0) 24 * bm = new BMatrix(2, 2, 1, 1); // 2-row 2-column binary matrix (1 0 ↓ 0 0) 25 * bm = new BMatrix(2, 2, 2, 1); // 2-row 2-column binary matrix (0 0 ↓ 1 0) 26 * @class Represents Binary Matrix 27 * @this {BMatrix} 28 * @property {Number} init number of initial values 29 * @property {Number} n number of rows 30 * @property {Number} m number of columns 31 * @property {BVector[]} colv substance of binary matrix 32 * @since 0.1 33 */ 34 BMatrix = function() { 35 this.init = arguments.length - 2; 36 if (this.init < 0) 37 return null; 38 this.n = arguments[0]; 39 this.m = arguments[1]; 40 this.colv = new Array(this.m); 41 this.clear(); 42 for (var k = 1; k <= this.init; k++) { 43 var i = arguments[k + 1][0]; 44 var j = arguments[k + 1][1]; 45 this.setValue(i, j, 1); 46 } 47 }; 48 49 BMatrix.prototype = { 50 /** 51 * Clears with zeroes with the binary matrix object 52 * @since 0.1 53 */ 54 clear : function() { 55 for (var j = 0; j < this.m; j++) { 56 if (this.colv[j] == undefined) 57 this.colv[j] = new BVector(this.n); 58 this.colv[j].clear(); 59 } 60 }, 61 62 /** 63 * Sets a value (0 or 1) to the element i,j of the binary matrix object 64 * @param {Number} i row number of the element to set (1 origin) 65 * @param {Number} j column number of the element to set (1 origin) 66 * @param {Number} value set value 0 or 1 67 * @since 0.1 68 */ 69 setValue : function(i, j, value) { 70 // convert to 0 origin 71 var j0 = j - 1; 72 this.colv[j0].setValue(i, value); 73 }, 74 75 /** 76 * Returns the value (0 or 1) of the element i,j of the binary matrix object 77 * @param {Number} i row number of the element to get (1 origin) 78 * @param {Number} j column number of the element to get (1 origin) 79 * @return {Number} value of the element i,j (0 or 1) 80 * @since 0.1 81 */ 82 getValue : function(i, j) { 83 // convert to 0 origin 84 var j0 = j - 1; 85 return this.colv[j0].getValue(i); 86 }, 87 88 /** 89 * Copies binary matrix 90 * @return {BMatrix} copy of the binary matrix 91 * @since 0.1 92 */ 93 clone : function() { 94 var bm = new BMatrix(this.n, this.m); 95 for (var j = 0; j < this.m; j++) 96 bm.colv[j] = this.colv[j].clone(); 97 return bm; 98 }, 99 100 /** 101 * Counts value 1 in the binary matrix object 102 * @return {Number} number of elements that have value 1 103 * @since 0.1 104 */ 105 abs : function() { 106 var n = 0; 107 for (var j = 0; j < this.m; j++) 108 n += this.colv[j].abs(); 109 return n; 110 }, 111 112 /** 113 * Returns inverted binary matrix object 114 * @return {BMatrix} inverted binary matrix 115 * @since 0.1 116 */ 117 inv : function() { 118 var bm = new BMatrix(this.n, this.m); 119 for (var j = 0; j < this.m; j++) { 120 bm.colv[j] = this.colv[j].inv(); 121 } 122 return bm; 123 }, 124 125 /** 126 * Returns transposed binary matrix 127 * @return {BMatrix} transposed binary matrix 128 * @return {BVector} column vector for row vector 129 * @since 0.4 130 */ 131 tran : function() { 132 if (this.n == 1) { 133 // row vector 134 var bv = new BVector(this.m); 135 for (var j = 1; j <= this.m; j++) { 136 bv.setValue(j, this.getValue(1, j)); 137 } 138 return bv; 139 } else { 140 var bm = new BMatrix(this.m, this.n); 141 for (var i = 1; i <= this.n; i++) { 142 for (var j = 1; j <= this.m; j++) { 143 bm.setValue(j, i, this.getValue(i, j)); 144 } 145 } 146 return bm; 147 } 148 }, 149 150 /** 151 * Returns true if two binary matrices are equal. Returns false if error or different. 152 * @param {BMatrix} bm2 comparison target binary matrix 153 * @return {boolean} true if two matrices are equal. 154 * @since 0.1 155 */ 156 equals : function(bm2) { 157 if (this.n != bm2.n || this.m != bm2.m) { 158 // different order 159 return false; 160 } 161 for (var j = 0; j < this.m; j++) { 162 if (!((this.colv[j]).equals(bm2.colv[j]))) { 163 // different value 164 return false; 165 } 166 } 167 return true; 168 }, 169 170 /** 171 * Logical or with binary matrix bm2 172 * @param {BMatrix} bm2 second operand for logocal or 173 * @return {BMatrix} logical or with bm2 (or null if error) 174 * @since 0.1 175 */ 176 or : function(bm2) { 177 if (this.n != bm2.n || this.m != bm2.m) { 178 // different order 179 return null; 180 } 181 var bm = new BMatrix(this.n, this.m); 182 for (var j = 0; j < this.m; j++) { 183 bm.colv[j] = this.colv[j].or(bm2.colv[j]); 184 } 185 return bm; 186 }, 187 188 /** 189 * Logical and with binary matrix bm2 190 * @param {BMatrix} bm2 second operand for logocal and 191 * @return {BMatrix} logical and with bm2 (or null if error) 192 * @since 0.1 193 */ 194 and : function(bm2) { 195 if (this.n != bm2.n || this.m != bm2.m) { 196 // different order 197 return null; 198 } 199 var bm = new BMatrix(this.n, this.m); 200 for (var j = 0; j < this.m; j++) { 201 bm.colv[j] = this.colv[j].and(bm2.colv[j]); 202 } 203 return bm; 204 }, 205 206 /** 207 * Logical difference with the binary matrix bm2 208 * @param {BMatrix} bm2 second operand for logical difference 209 * @return {BMatrix} logical difference with bm2 (or null if error) 210 * @since 0.1 211 */ 212 diff : function(bm2) { 213 if (this.n != bm2.n || this.m != bm2.m) { 214 // different order 215 return null; 216 } 217 var bm = new BMatrix(this.n, this.m); 218 for (var j = 0; j < this.m; j++) { 219 bm.colv[j] = this.colv[j].diff(bm2.colv[j]); 220 } 221 return bm; 222 }, 223 224 /** 225 * Exclusive or with the binary matrix bm2 226 * @param {BMatrix} bm2 second operand for exclusive or 227 * @return {BMatrix} exclusive or with bm2 (or null if error) 228 * @since 0.1 229 */ 230 xor : function(bm2) { 231 if (this.n != bm2.n || this.m != bm2.m) { 232 // different order 233 return null; 234 } 235 var bm = new BMatrix(this.n, this.m); 236 for (var j = 0; j < this.m; j++) { 237 bm.colv[j] = this.colv[j].xor(bm2.colv[j]); 238 } 239 return bm; 240 }, 241 242 /** 243 * Product with given binary matrix (or binary vector) 244 * @param {BMatrix | BVector} bx2 second operand for product 245 * @return {BMatrix} product with bx2 (or null if error) 246 * @since 0.1 247 */ 248 mul : function(bx2) { 249 if (bx2.n == undefined) { 250 // bx2 is vector 251 if (this.m != bx2.order) 252 return null; 253 var bv = new BVector(bx2.order); 254 for (var k = 0; k < this.m; k++) { 255 if (bx2.getValue(k + 1) == 1) 256 bv = bv.or(this.colv[k]); 257 } 258 return bv; 259 } else { 260 // bx2 is matrix 261 if (this.m != bx2.n) 262 return null; 263 var bm = new BMatrix(bx2.n, bx2.m); 264 for (var j = 0; j < bx2.m; j++) { 265 for (var k = 0; k < this.m; k++) { 266 if (bx2.getValue(k + 1, j + 1) == 1) 267 bm.colv[j] = bm.colv[j].or(this.colv[k]); 268 } 269 } 270 return bm; 271 } 272 }, 273 274 /** 275 * Convert the binary matrix to a string 276 * @return {String} string 277 * @since 0.1 278 */ 279 toString : function() { 280 var str = ""; 281 for (var i = 1; i <= this.n; i++) { 282 for (var j = 1; j <= this.m; j++) { 283 str = str + this.getValue(i, j); 284 if (j < this.m) 285 str = str + " "; 286 } 287 str = str + "\n"; 288 } 289 return str; 290 }, 291 292 /** 293 * Convert the binary matrix to TeX string 294 * @return {String} TeX string 295 * @since 0.1 296 */ 297 toTeX : function() { 298 var str = "\\begin{pmatrix}"; 299 for (var i = 1; i <= this.n; i++) { 300 for (var j = 1; j <= this.m; j++) { 301 str = str + this.getValue(i, j); 302 if (j < this.m) 303 str = str + " & "; 304 } 305 if (i < this.n) 306 str = str + "\\\\"; 307 } 308 str = str + "\\end{pmatrix}"; 309 return str; 310 } 311 }; 312